Halftone imaging, sometimes referred to as xe2x80x9chalftoning,xe2x80x9d is a well-known technique for transforming a continuous tone original image (e.g., a photograph) into a halftone image having pixels that are either black (presence of a mark or xe2x80x9cdotxe2x80x9d) or white (absence of a mark or xe2x80x9cdotxe2x80x9d). Although the absence of a black dot can be considered a white dot, for ease of discussion, the term xe2x80x9cdotxe2x80x9d, as used herein, refers to the presence of a black dot.
In general, many halftoning algorithms modulate the density or clustering of the dots of the halftone image based upon the gray scale value for each pixel of the original image. Typically, halftone image processing entails a decision to print or not print a dot for each pixel of the halftone image. Whether a dot is printed or not, the halftone value of each pixel of the halftone image will have some level of quantization error, except in the instances where the corresponding pixel of the original image is black or white.
Error diffusion techniques have been developed in order to spread or diffuse the quantization errors that result from halftone imaging over neighboring pixels of the halftone image, to thereby make the quantization error or noise inherent in the halftone image as imperceptible as possible to the human eye. In essence, error diffusion is a type of noise filtering which shapes the quantization error or noise inherent in the quantization (digitization) of the original continuous tone image, e.g., by shifting the quantization noise from a low frequency domain that is perceptible to the human eye to a high frequency domain that is less perceptible (or imperceptible) to the human eye.
Some imaging devices cannot stably or reliably produce dots beyond a certain horizontal dot resolution. For example, some laser printers operate in an enhanced resolution imaging mode, sometimes referred to as a High Definition Imaging (HDI) mode, in which the laser horizontal scan line of the normal resolution mode is subdivided into finer increments, whereby the laser printer produces dots during correspondingly shorter laser on/off cycles. In other words, the pixel of the halftone image produced by the laser printer in the enhanced resolution mode is subdivided into sub-pixels. If the normal horizontal resolution mode of a laser printer is 600 dots per inch (dpi), and the enhanced horizontal resolution mode of that laser printer is 2,400 dpi, then each pixel of the halftone image produced by that laser printer in the enhanced horizontal resolution mode is subdivided into 4 sub-pixels, so that the laser on/off cycle in the enhanced horizontal resolution mode is xc2xcth the laser on/off cycle in the normal horizontal resolution mode. However, the laser printer might not be capable of stably or reliably printing isolated xe2x80x9csub-pixel dotsxe2x80x9d at that sub-pixel resolution. Such instability of the laser printer or other image forming device is referred to herein as xe2x80x9cdot instabilityxe2x80x9d.
Dot instability results in perceptible visual anomalies or quantization noise in the resultant half-tone image produced by the laser printer due to the absence of dots at pixel or sub-pixel locations where dots are supposed to be present. For example, some laser printers, when operating in an enhanced horizontal dot resolution mode, experience severe single sub-pixel dot instability, but are able to print two or more adjacent sub-pixel dots in a reliable and stable manner. Other laser printers might only be capable of printing a minimum of three or more adjacent sub-pixel dots in a reliable and stable manner. In general, a pixel or sub-pixel dot is considered to be xe2x80x9cisolatedxe2x80x9d if it is not adjacent to at least Mxe2x88x921 previous pixel or sub-pixel dots in the laser scan direction, where M is the minimum number of pixel or sub-pixel dots that the laser printer can reliably and stably produce.
Some known error diffusion halftoning algorithms incorporate soft dot stability constraints to force a certain level of dot clustering in an attempt to minimize perceptible quantization noise in the halftone image attributable to dot instability of the image forming device. For example, some soft dot stability constraints ensure that a minimum average number of dots are produced, or impose some other global parametric constraint regarding dot clustering. However, such error diffusion halftoning algorithms do not eliminate isolated dots in the halftone image, without excessive dot clustering.
According to one aspect of the present invention, an output halftone image is formed from an input image having a plurality of input image pixels. The output image is formed by processing the input image pixels with a halftoning process that incorporates a hard dot stability constraint. The halftoning process forces a determination to produce a dot for each of M output halftone image pixels following an output halftone image pixel dot that would otherwise be isolated, where Mxe2x89xa71.
Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the present invention.